package com.kobeliu.entity;

public class HeapSort {

    public static void main(String[] args) {

        int[] nums = {4,-1,4,2,63,213,2,6,32,9,213
                ,434,6,434,326,34,234324,3423,343,323,64,74,23,634
        ,332,63,634,734,64,779,3432,723,6234,735,3324,62334,3242,62234,62334,34};

        HeapSortFunction(nums);
    }

    private static void HeapSortFunction(int[] nums) {

        long l = System.currentTimeMillis();
        int heapSize = nums.length;
        heapInsert(nums,heapSize); //O(logn)
        swap(nums,0,--heapSize);

        while (heapSize >0){
            heapify(nums,0,heapSize);
            swap(nums,0,--heapSize);
        }
        System.out.println(System.currentTimeMillis()-l);


    }

    private static void heapify(int[] nums,int start,int heapSize) {

        int num = 0;
        while(start<heapSize) {
            if(2*start+1 > heapSize) break;
            if(2*start+2 <= heapSize){
                num = nums[2*start+1]>=nums[2*start+1]?2*start+1:2*start+2;
                if(num>nums[start]) swap(nums,start,num);
                else break;
            }
            if(2*start+1 > heapSize){
                
            }
        }
    }

    private static void heapInsert(int[] nums, int heapSize) {
        int i = 1;
        int k = 0;
        while(i<heapSize){
            k = i;
            while(nums[k] > nums[(k-1)/2]){
                swap(nums,k,(k-1)/2);
                k = (k-1)/2;
            }
            i++;
        }

    }

    private static void swap(int[] nums, int k, int i) {
        int temp = 0;
        temp = nums[k];
        nums[k] = nums[i];
        nums[i] = temp;
    }
}
